/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	src/hash.c
 * @brief       A collection of hash functions.
 *
 * @see		dlib
 * @history
 *	      version 0.1.0, Spark init hash module
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>

#include "hash.h"

uint32_t simple_hash(const void* key, int key_len)
{
	uint32_t h = 0;
	const unsigned char *p;
	const unsigned char *p_end;

	p_end = (const unsigned char *)key + key_len;
	for (p = (const unsigned char *)key; p!= p_end; p++)
	{
		h = 31 * h + *p;
	}

	return h;
}

uint32_t one_at_a_time_hash(const char *k, uint32_t len)
{
	uint32_t hash;
	uint32_t i;

	for (hash = 0, i = 0; i < len; i++) {
		hash += (uint32_t)k[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}
	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash;
}


uint32_t elf_hash(const char *k, uint32_t len)
{
	uint32_t hash = 0;
	uint32_t temp;
	uint32_t i;

	for (i = 0; i < len; i++) {
		hash = (hash << 4) + (uint32_t) (k[i]);
		if ((temp = (hash & 0xF0000000UL)) != 0) {
			hash ^= (temp >> 24);
		}
		hash &= ~temp;
	}

	return hash;
}

/**
 * ext_dx_hack_hash
 * @brief ext2/3/4 filesystem legacy dir hash function
 * @param name: dir name
 * @param len: dir-string length
 */
uint32_t ext_dx_hack_hash (const char *k, int len)
{
	uint32_t hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
	while (len--) {
		uint32_t hash = hash1 + (hash0 ^ (*k++ * 7152373));
		if (hash & 0x80000000)
			hash -= 0x7fffffff;
		hash1 = hash0;
		hash0 = hash;
	}
	return (hash0 << 1);
}

/**
 * Base 31 hash function. Taken from Gnome's glib, modified to use
 *  standard C types.
 *
 * We used to use the popular hash function from the Dragon Book, but
 * this one seems to perform much better, both by being faster and by
 * generating less collisions.
 */
uint32_t glib_string_hash (const void *key)
{
	const char *p = key;
	uint32_t h = *p;
  
	if (h) {
		for (p += 1; *p != '\0'; p++)
			h = (h << 5) - h + *p;
	}
  
	return h;
}

/**
 * Hashing of numeric values, such as pointers and integers.
 *
 * This implementation is the Robert Jenkins' 32 bit Mix Function,
 * with a simple adaptation for 64-bit values.  According to Jenkins
 * it should offer excellent spreading of values.  Unlike the popular
 * Knuth's multiplication hash, this function doesn't need to know the
 * hash table size to work.
 */
#ifndef SIZEOF_VOID_P
#define SIZEOF_VOID_P	4
#endif
unsigned long glib_pointer_hash(const void *ptr)
{
	uintptr_t key = (uintptr_t) ptr;
	key += (key << 12);
	key ^= (key >> 22);
	key += (key << 4);
	key ^= (key >> 9);
	key += (key << 10);
	key ^= (key >> 2);
	key += (key << 7);
	key ^= (key >> 12);
#if SIZEOF_VOID_P > 4
	key += (key << 44);
	key ^= (key >> 54);
	key += (key << 36);
	key ^= (key >> 41);
	key += (key << 42);
	key ^= (key >> 34);
	key += (key << 39);
	key ^= (key >> 44);
#endif
	return (unsigned long) key;
}

uint32_t rs_hash(const void *key, int key_len)
{
	const unsigned char *p_key;
	const unsigned char *p_end;
	uint32_t b = 378551;
	uint32_t a = 63689;
	uint32_t hash = 0;

	p_end = (const unsigned char *)key + key_len;
	for (p_key = (const unsigned char *)key; p_key != p_end; p_key++) {
		hash = hash * a + (*p_key);
		a *= b;
	}

	return hash;
} 

uint32_t js_hash(const void *key, int key_len)
{
	const unsigned char *p_key;
	const unsigned char *p_end;
	uint32_t hash = 1315423911;

	p_end = (const unsigned char *)key + key_len;
	for (p_key = (const unsigned char *)key; p_key != p_end; p_key++){
		hash ^= ((hash << 5) + (*p_key) + (hash >> 2));
	}

	return hash;
}

uint32_t sdbm_hash(const void *key)
{
	uint32_t hash = 0;
	int c;
	const unsigned char *tmp = (const unsigned char *)key;

	while ((c = *tmp++) != '\0') {
    		hash = c + (hash << 6) + (hash << 16) - hash;
	}

	return hash;
}

uint32_t bkdr_hash(const void *key, int key_len)
{
	const unsigned char *p_key;
	const unsigned char *p_end;
	uint32_t seed = 131;
	uint32_t hash = 0;

	p_end = (const unsigned char *)key + key_len;
	for (p_key = (const unsigned char *)key; p_key != p_end; p_key++) {
		hash = hash * seed + (*p_key);
	}

	return hash;
}

/**
 * djb2 hashing algorithm by Dan Bernstein. From:
 * http://www.cse.yorku.ca/~oz/hash.html
 */
uint32_t djb_hash(const void *key)
{
	uint32_t hash = 5381;
	int c;
	const unsigned char *tmp = (const unsigned char *)key;

	while ((c = *tmp++) != '\0')
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

	return hash;
}

uint32_t r5_hash(const void *key)
{
	uint32_t hash = 0;
	int c;
	const unsigned char *tmp = (const unsigned char *)key;

	c = *tmp;
	while (c) {
		hash = (hash + (c << 4) + (c >> 4)) * 11;
		c = *++tmp;
	}
	return hash;
}

uint32_t ap_hash(const void *key, int key_len)
{
	const unsigned char *p_key;
	const unsigned char *p_end;
	uint32_t hash = 0;
	uint32_t i;

	p_end = (const unsigned char *)key + key_len;
	for (p_key = (const unsigned char *)key, i=0; p_key != p_end;
	     p_key++, i++) {
		if ((i & 1) == 0) {
			hash ^= ((hash << 7) ^ (*p_key) ^ (hash >> 3));
		} else {
			hash ^= (~((hash << 11) ^ (*p_key) ^ (hash >> 5)));
		}
	}

	return hash;
}

uint32_t calc_hash(const void* key, int key_len)
{
	const unsigned char *p_key;
	const unsigned char *p_end;
	uint32_t nr = 1, nr2 = 4;

	p_end = (const unsigned char *)key + key_len;
	for (p_key = (const unsigned char *)key; p_key != p_end; p_key++) {
		nr ^= (((nr & 63) + nr2) * (*p_key)) + (nr << 8);
		nr2 += 3;
	}

	return nr;
}

/**
 * perfect-hash: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 * http://burtleburtle.net/bob/c/lookup3.c
 * 1. perfect_word_hash
 * 2. perfect_word2_hash
 * 3. perfect_hash
 * 4. perfect2_hash
 */
/**
 * My best guess at if you are big-endian or little-endian.  This may
 * need adjustment.
 */
#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
	__BYTE_ORDER == __LITTLE_ENDIAN) || \
	(defined(i386) || defined(__i386__) || defined(__i486__) || \
	defined(__i586__) || defined(__i686__) || defined(vax) || \
	defined(MIPSEL))
#define HASH_LITTLE_ENDIAN		1
#define HASH_BIG_ENDIAN			0
#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
	__BYTE_ORDER == __BIG_ENDIAN) || \
	(defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
#define HASH_LITTLE_ENDIAN		0
#define HASH_BIG_ENDIAN			1
#else
#define HASH_LITTLE_ENDIAN		0
#define HASH_BIG_ENDIAN			0
#endif

/**
 * perfect_word_hash
 * This works on all machines.  To be useful, it requires
 * -- that the key be an array of uint32_t's, and
 * -- that the length be the number of uint32_t's in the key

 * The function hashword() is identical to hashlittle() on little-endian
 * machines, and identical to hashbig() on big-endian machines,
 * except that the length has to be measured in uint32_ts rather than in
 * bytes.  hashlittle() is more complicated than hashword() only because
 * hashlittle() has to dance around fitting the key bytes into registers.
 *
 * @param k: the key, an array of uint32_t values
 * @param length: the length of the key, in uint32_ts
 * @param initval: the previous hash, or an arbitrary value
 */
uint32_t perfect_word_hash(const uint32_t *k, uint32_t length, uint32_t initval)
{
	uint32_t a, b, c;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + (length << 2) + initval;

/*------------------------------------------------- handle most of the key */
	while (length > 3) {
		a += k[0];
		b += k[1];
		c += k[2];
		HASH_MIX32(a, b, c);
		length -= 3;
		k += 3;
	}

/*------------------------------------------- handle the last 3 uint32_t's */
	/* all the case statements fall through */
	switch(length) { 
		case 3: c+=k[2];
		case 2: b+=k[1];
		case 1: a+=k[0];
			HASH_FINAL32(a, b, c);
		case 0:
			break;
	}
/*------------------------------------------------------ report the result */
	
	return c;
}

/**
 * perfect_word2_hash
 * hashword2() -- same as hashword(), but take two seeds and return two
 * 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
 * both be initialized with seeds.  If you pass in (*pb)==0, the output 
 * (*pc) will be the same as the return value from hashword().
 *
 * @param k: the key, an array of uint32_t values
 * @param length: the length of the key, in uint32_ts
 * @param pc[IN]: seed OUT: primary hash value
 * @param pb[IN]: more seed OUT: secondary hash value
 */
void perfect_word2_hash(const uint32_t *k, uint32_t length,
			uint32_t *pc, uint32_t *pb)
{
	uint32_t a, b, c;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + (length << 2) + *pc;
	c += *pb;
	
/*------------------------------------------------- handle most of the key */
	while (length > 3) {
		a += k[0];
		b += k[1];
		c += k[2];
		HASH_MIX32(a, b, c);
		length -= 3;
		k += 3;
	}

/*------------------------------------------- handle the last 3 uint32_t's */
	/* all the case statements fall through */
	switch(length) { 
		case 3: c+=k[2];
		case 2: b+=k[1];
		case 1: a+=k[0];
			HASH_FINAL32(a, b, c);
		case 0:
			break;
	}
/*------------------------------------------------------ report the result */
	
	*pc = c;
	*pb = b;
	
	return;
}

/**
 * perfect_hash
 * hashlittle() -- hash a variable-length key into a 32-bit value
 * Returns a 32-bit value.  Every bit of the key affects every bit of
 * the return value.  Two keys differing by one or two bits will have
 * totally different hash values.

 * The best hash table sizes are powers of 2.  There is no need to do
 * mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 * use a bitmask.  For example, if you need only 10 bits, do
 *   h = (h & hashmask(10));
 * In which case, the hash table should have hashsize(10) elements.

 * If you are hashing n strings (uint8_t **)k, do it like this:
 *  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);

 * By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 * code any way you wish, private, educational, or commercial.  It's free.

 * Use for hash table lookup, or anything where one collision in 2^^32 is
 * acceptable.  Do NOT use for cryptographic purposes.
 *
 * @param k: the key (the unaligned variable-length array of bytes)
 * @param length: the length of the key, counting by bytes
 * @param initval: can be any 4-byte value
 */
uint32_t perfect_hash(const void *key, uint32_t length, uint32_t initval)
{
	uint32_t a, b, c;
	/* needed for Mac Powerbook G4 */
	union { const void *ptr; size_t i; } u;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + length + initval;

	u.ptr = key;
	if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
		const uint32_t *k = (const uint32_t *)key;

/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
		while (length > 12) {
			a += k[0];
			b += k[1];
			c += k[2];
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 3;
		}

/*----------------------------- handle the last (probably partial) block */
/* 
 * "k[2]&0xffffff" actually reads beyond the end of the string, but
 * then masks off the part it's not allowed to read.  Because the
 * string is aligned, the masked-off tail is in the same word as the
 * rest of the string.  Every machine with memory protection I've seen
 * does it on word boundaries, so is OK with this.  But VALGRIND will
 * still catch it and complain.  The masking trick does make the hash
 * noticably faster for short strings (like English words).
 */
#ifndef VALGRIND
		
		switch(length) {
			case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
			case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
			case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
			case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
			case 8 : b+=k[1]; a+=k[0]; break;
			case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
			case 6 : b+=k[1]&0xffff; a+=k[0]; break;
			case 5 : b+=k[1]&0xff; a+=k[0]; break;
			case 4 : a+=k[0]; break;
			case 3 : a+=k[0]&0xffffff; break;
			case 2 : a+=k[0]&0xffff; break;
			case 1 : a+=k[0]&0xff; break;
			case 0 : return c;
		}

#else /* make valgrind happy */

		const uint8_t  *k8;
		
		k8 = (const uint8_t *)k;
		switch(length)
		{
			case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
			case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
			case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
			case 9 : c+=k8[8];		   /* fall through */
			case 8 : b+=k[1]; a+=k[0]; break;
			case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
			case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
			case 5 : b+=k8[4];		   /* fall through */
			case 4 : a+=k[0]; break;
			case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
			case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
			case 1 : a+=k8[0]; break;
			case 0 : return c;
		}

#endif /* !valgrind */

	} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
		const uint16_t *k = (const uint16_t *)key;
		const uint8_t  *k8;

/*--------------- all but last block: aligned reads and different mixing */
		while (length > 12) {
			a += k[0] + (((uint32_t)k[1])<<16);
			b += k[2] + (((uint32_t)k[3])<<16);
			c += k[4] + (((uint32_t)k[5])<<16);
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 6;
		}

/*----------------------------- handle the last (probably partial) block */
		k8 = (const uint8_t *)k;
		switch(length) {
			case 12:
				c+=k[4]+(((uint32_t)k[5])<<16);
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 11:
				c+=((uint32_t)k8[10])<<16;
			case 10:
				c+=k[4];
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 9 :
				c+=k8[8]; /* fall through */
			case 8 :
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 7 :
				b+=((uint32_t)k8[6])<<16;
			case 6 :
				b+=k[2];
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 5 :
				b+=k8[4]; /* fall through */
			case 4 :
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 3 :
				a+=((uint32_t)k8[2])<<16; /* fall through */
			case 2 :
				a+=k[0];
				break;
			case 1 :
				a+=k8[0];
				break;
			case 0 :
				return c;
		}
	} else { /* need to read the key one byte at a time */
		const uint8_t *k = (const uint8_t *)key;

/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
		while (length > 12) {
			a += k[0];
			a += ((uint32_t)k[1])<<8;
			a += ((uint32_t)k[2])<<16;
			a += ((uint32_t)k[3])<<24;
			b += k[4];
			b += ((uint32_t)k[5])<<8;
			b += ((uint32_t)k[6])<<16;
			b += ((uint32_t)k[7])<<24;
			c += k[8];
			c += ((uint32_t)k[9])<<8;
			c += ((uint32_t)k[10])<<16;
			c += ((uint32_t)k[11])<<24;
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 12;
		}

/*-------------------------------- last block: affect all 32 bits of (c) */
		switch(length) {
			case 12: c+=((uint32_t)k[11])<<24;
			case 11: c+=((uint32_t)k[10])<<16;
			case 10: c+=((uint32_t)k[9])<<8;
			case 9 : c+=k[8];
			case 8 : b+=((uint32_t)k[7])<<24;
			case 7 : b+=((uint32_t)k[6])<<16;
			case 6 : b+=((uint32_t)k[5])<<8;
			case 5 : b+=k[4];
			case 4 : a+=((uint32_t)k[3])<<24;
			case 3 : a+=((uint32_t)k[2])<<16;
			case 2 : a+=((uint32_t)k[1])<<8;
			case 1 : a+=k[0]; break;
			case 0 : return c;
		}
	}

	HASH_FINAL32(a, b, c);
	
	return c;
}

/**
 * perfect2_hash
 * hashlittle2: return 2 32-bit hash values
 *
 * This is identical to hashlittle(), except it returns two 32-bit hash
 * values instead of just one.  This is good enough for hash table
 * lookup with 2^^64 buckets, or if you want a second hash if you're not
 * happy with the first, or if you want a probably-unique 64-bit ID for
 * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
 *
 * @param key: the key to hash
 * @param length: length of the key
 * @param pc: IN: primary initval, OUT: primary hash
 * @param pb: IN: secondary initval, OUT: secondary hash
 */
void perfect2_hash(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
{
	uint32_t a,b,c;
	/* needed for Mac Powerbook G4 */
	union { const void *ptr; size_t i; } u;

	/* Set up the internal state */
	a = b = c = 0xdeadbeef + length + *pc;
	c += *pb;

	u.ptr = key;
	if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
		const uint32_t *k = (const uint32_t *)key;
		
/*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
		while (length > 12) {
			a += k[0];
			b += k[1];
			c += k[2];
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 3;
		}

/*----------------------------- handle the last (probably partial) block */
/** 
 * "k[2]&0xffffff" actually reads beyond the end of the string, but
 * then masks off the part it's not allowed to read.  Because the
 * string is aligned, the masked-off tail is in the same word as the
 * rest of the string.  Every machine with memory protection I've seen
 * does it on word boundaries, so is OK with this.  But VALGRIND will
 * still catch it and complain.  The masking trick does make the hash
 * noticably faster for short strings (like English words).
 */
#ifndef VALGRIND

		switch(length) {
			case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
			case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
			case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
			case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
			case 8 : b+=k[1]; a+=k[0]; break;
			case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
			case 6 : b+=k[1]&0xffff; a+=k[0]; break;
			case 5 : b+=k[1]&0xff; a+=k[0]; break;
			case 4 : a+=k[0]; break;
			case 3 : a+=k[0]&0xffffff; break;
			case 2 : a+=k[0]&0xffff; break;
			case 1 : a+=k[0]&0xff; break;
			case 0 : *pc=c; *pb=b; return;
		}

#else /* make valgrind happy */

		const uint8_t  *k8;
		
		k8 = (const uint8_t *)k;
		switch(length) {
			case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
			case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
			case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
			case 9 : c+=k8[8];		   /* fall through */
			case 8 : b+=k[1]; a+=k[0]; break;
			case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
			case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
			case 5 : b+=k8[4];		   /* fall through */
			case 4 : a+=k[0]; break;
			case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
			case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
			case 1 : a+=k8[0]; break;
			case 0 : *pc=c; *pb=b; return;
		}

#endif /* !valgrind */

	} else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
		const uint16_t *k = (const uint16_t *)key;
		const uint8_t  *k8;

/*--------------- all but last block: aligned reads and different mixing */
		while (length > 12) {
			a += k[0] + (((uint32_t)k[1])<<16);
			b += k[2] + (((uint32_t)k[3])<<16);
			c += k[4] + (((uint32_t)k[5])<<16);
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 6;
		}

/*----------------------------- handle the last (probably partial) block */
		k8 = (const uint8_t *)k;
		switch(length) {
			case 12:
				c+=k[4]+(((uint32_t)k[5])<<16);
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
			case 10:
				c+=k[4];
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 9 : c+=k8[8]; /* fall through */
			case 8 :
				b+=k[2]+(((uint32_t)k[3])<<16);
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 7 : b+=((uint32_t)k8[6])<<16;  /* fall through */
			case 6 :
				b+=k[2];
				a+=k[0]+(((uint32_t)k[1])<<16);
				break;
			case 5 : b+=k8[4]; /* fall through */
			case 4 : a+=k[0]+(((uint32_t)k[1])<<16); break;
			case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
			case 2 : a+=k[0]; break;
			case 1 : a+=k8[0]; break;
			case 0 : *pc=c; *pb=b; return;
		}
	} else { /* need to read the key one byte at a time */
		const uint8_t *k = (const uint8_t *)key;

/*--------------- all but the last block: affect some 32 bits of (a,b,c) */
		while (length > 12) {
			a += k[0];
			a += ((uint32_t)k[1])<<8;
			a += ((uint32_t)k[2])<<16;
			a += ((uint32_t)k[3])<<24;
			b += k[4];
			b += ((uint32_t)k[5])<<8;
			b += ((uint32_t)k[6])<<16;
			b += ((uint32_t)k[7])<<24;
			c += k[8];
			c += ((uint32_t)k[9])<<8;
			c += ((uint32_t)k[10])<<16;
			c += ((uint32_t)k[11])<<24;
			HASH_MIX32(a, b, c);
			length -= 12;
			k += 12;
		}

/*-------------------------------- last block: affect all 32 bits of (c) */
		switch(length) {
			case 12: c+=((uint32_t)k[11])<<24;
			case 11: c+=((uint32_t)k[10])<<16;
			case 10: c+=((uint32_t)k[9])<<8;
			case 9 : c+=k[8];
			case 8 : b+=((uint32_t)k[7])<<24;
			case 7 : b+=((uint32_t)k[6])<<16;
			case 6 : b+=((uint32_t)k[5])<<8;
			case 5 : b+=k[4];
			case 4 : a+=((uint32_t)k[3])<<24;
			case 3 : a+=((uint32_t)k[2])<<16;
			case 2 : a+=((uint32_t)k[1])<<8;
			case 1 : a+=k[0]; break;
			case 0 : *pc=c; *pb=b; return;
		}
	}

	HASH_FINAL32(a, b, c);
	*pc=c; *pb=b;
	
	return;
}
